Database systems typically store database objects (e.g. tables, indexes, etc.) on disk, and load data items from those database objects into volatile memory on an as-needed basis. Once loaded into volatile memory, the data items may remain cached in volatile memory so that subsequent accesses to the same data items will not incur the overhead of accessing a disk. Those data items may be replaced in cache, for example, to make room in volatile memory to store other data items that have been requested.
Rather than load individual data items on a per-item basis, entire database objects, or portions thereof, may be loaded into volatile memory. Various approaches for loading entire database objects, or selected portions thereof, into volatile memory to speed up query processing are described in U.S. patent application Ser. No. 14/377,179, entitled “Mirroring, In Memory, Data From Disk To Improve Query Performance”, filed Jul. 21, 2014, the contents of which are incorporated herein in its entirety (hereinafter, the “Mirroring application”).
According to the approaches described in the Mirroring application, data objects, or portions thereof, are stored in volatile memory in a different format than the format that those same objects have on disk. For example, the in-memory version of the objects may be in a column-major format, while the on-disk version stored data in a row-major format. The in-memory version of the object (or selected portions thereof), is referred to as an In-Memory Compression Unit (IMCU) because the data contained therein is often compressed.
In a clustered database system, multiple “server nodes” have access to the same on-disk copy of a database. Typically, each server node is a computing device with its own local volatile memory and processors. Each server node typically runs its own distinct instance, or set of instances, of the database server. Queries that target the shared database may be sent to any database server instance on any of the server nodes.
The speed at which a given database server instance is able to answer a query is based, at least in part, on whether the server node on which the database server instance is running has, within its local volatile memory, an IMCU that contains the data targeted by the query. For example, a query “select c1 from emp where c2>10” may be executed much faster on a server node that hosts an IMCU with values from c1 and c2 of the emp table, than on a server node that has no IMCU containing data targeted by the query.
Thus, in order to determine whether a particular database server instance would be best at processing a query, it is necessary to quickly determine whether data targeted by the query is in any IMCU within the local volatile memory of that particular database server instance. According to one embodiment, a database server instance that receives a query searches a metadata directory map to determine whether or not the data targeted by a query is in a local IMCU. In one embodiment, the database server instance provides an on-disk address for the data targeted by the query (the “target data”). The on-disk address of the target data shall be referred to hereafter as the “target on-disk address”.
A metadata directory map is a lookup directory that, for any given target data, maps the on-disk address of target data to an in-memory address of the IMCU that contains the target data. In order for a server node to quickly determine the location of IMCUs, the metadata directory map is stored within the local volatile memory of the server node. When the database server receives a query that requires accessing particular target data stored at a target on-disk address, the database server uses the metadata directory map to lookup the memory location of the IMCU that contains the particular target data. The memory location provided by the metadata directory map indicates the physical address, within local volatile memory, of the IMCU that contains the target data.
For example, assume that a database server instance receives a query that targets columns c1 and c2 of table emp. Assume further that table emp is located on disk at address X. Thus, X is the target on-disk address. Under these circumstances, the database server instance would use address X as the key for looking up the in-memory address of the IMCU that contains columns c1 and c2 of table emp. For the purpose of discussion, assume that the IMCU that contains columns c1 and c2 of table emp is located at address Y within the volatile memory of the database server on which the database server instance is executing. Consequently, the metadata directory map would return “address Y” based on the address X.
A variety of different data structures may be used to implement the metadata directory map. For example, the metadata directory map may be implemented as a tree structure. An approach to implementing a metadata directory map using a tree structure is to have each node within the tree structure represent a particular range of on-disk data. For example, the root node may be defined as the on-disk address range for all data represented by the tree structure. Thus, if the tree structure is being used to represent a particular tablespace within a database, the root node of the tree structure would represent the entire on-disk address range of that tablespace.
Each of the child nodes of any given parent node represent a distinct sub-range of the range represented by the parent node. For instance, if the root node corresponds to a tablespace that has the size of 128 terabytes (TB), then the root node would represent the on-disk range from 0-128 TB. If the root node had a total of 128 child nodes, then each child node would represent a distinct sub-range, each of which would have the size of 1 TB. Subsequent child nodes at each level would then represent smaller sub-ranges of their respective parent node. A leaf node at the end of any given branch represents the smallest sub-range of all nodes that belong to that branch.
Various approaches have been used to populate metadata directory maps that have been implemented as tree structures, as described above. One such approach to populating the metadata directory map is to store, within the leaf nodes that implement the metadata directory, the in-memory address for a given IMCU that is loaded into local volatile memory of a server node. The server node first determines the on-disk address range of the loaded IMCU. Then the server node finds all leaf nodes, within the metadata directory map, that fall within the on-disk address range of the loaded IMCU. The server node then populates each leaf node that falls within the on-disk address range of the loaded IMCU with the in-memory address corresponding to the starting location of the loaded IMCU in local volatile memory.
For example, assume the server node loaded an IMCU containing target columns c1 and c2 from table emp. To keep the directory map up-to-date, the directory map would have to be updated to reflect that the on-disk addresses for columns c1 and c2 of table emp are mapped to the in-memory address of the newly-loaded IMCU.
For the purpose of explanation, it shall be assumed that table emp starts at on-disk address 32 KB. However, it is insufficient to merely map the starting address of table emp to the in-memory address of the IMCU, because all on-disk addresses covered by table emp need to be mapped to the newly-loaded IMCU.
Consequently, the server node would first determine the entire on-disk address range of the IMCU. For the purpose of explanation, it shall be assumed that on-disk address range of the IMCU covers the range of 32 KB-2048 KB. Then, the server node would locate all leaf nodes, within the directory map, that fall within the on-disk address range of 32 KB-2048 KB. Assume that each leaf node in the directory map represents a range of 32 KB. The server node would then find a set of leaf nodes that cover the range of 32 KB-2048 KB. Then, the server node would populate each leaf node, in the set of leaf nodes that cover the range of 32 KB-2048 KB, with the in-memory starting address of the loaded IMCU.
The drawback to this approach is that redundant mapping information corresponding to the in-memory starting address of the loaded IMCU is populated into every single leaf node that represents an on-disk address range that falls within the on-disk address range of the loaded IMCU. If the IMCU covers a particularly large on-disk address range, then the set of leaf nodes that contain the same mapping information becomes very large as well. Since the metadata directory map is stored within local volatile memory of the server node, this results in the server node having less local volatile memory space to store other things, such as additional IMCUs.
Another approach to populating the metadata directory map is to only populate leaf nodes that correspond to the on-disk starting address and the on-disk ending address of the loaded IMCU. In this approach, the server node, for a loaded IMCU, determines the on-disk starting address and on-disk ending address for the loaded IMCU. Then, the server node finds leaf nodes that correspond to the on-disk starting address and the on-disk ending address. The server node then populates only these two leaf nodes with (a) the in-memory address of the loaded IMCU, and (b) the on-disk address range of the IMCU. By also populating the on-disk address range of the IMCU, when searching for target data the server node can use the target on-disk address and the on-disk address range of the IMCU to determine whether target data is loaded into the particular IMCU. To determine whether target data is loaded into a particular IMCU, the server node first finds the leaf node that corresponds to the target on-disk address. If the leaf node does not contain any mapping information, then the server node scans preceding leaf nodes until it finds mapping information to an IMCU. Once the server node finds mapping information for an IMCU in a leaf node, the server node determines whether this IMCU covers a range that includes the target on-disk address.
For example, assume the server node loaded an IMCU covering a range of 32 KB-2048 KB and that each leaf node in the directory map represents a range of 32 KB. The server node would first determine that the on-disk starting address for the loaded IMCU is 32 KB and the on-disk ending address is 2048 KB. The server node would then find the leaf node that represents a range covering the on-disk starting address (32 KB) and the leaf node that represents a range covering the on-disk ending address (2048 KB). Then the server node would populate these two leaf nodes with the in-memory starting address of the loaded IMCU and the on-disk address range of the loaded IMCU (32 KB-2048 KB).
Based upon the current example, if the server node received a request for target data corresponding to a target on-disk address of 102,400 KB (100 MB), the server node would find the leaf node corresponding to a range covering 102,400 KB. Since the leaf node corresponding to 102,400 KB does not contain any mapping information, the server node would then begin scanning preceding leaf nodes. For example, the server node would first scan the leaf node corresponding to 102,368 KB (immediately preceding leaf node) for mapping information. The server node would continue to scan each preceding leaf node until it reaches a leaf node with mapping information (the leaf node corresponding to 2048 KB). Since the 2048 KB leaf node contains mapping information, the server node would determine based upon the on-disk address range of the loaded IMCU (32 KB-2048 KB) whether or not the loaded IMCU contains the target on-disk address. Here, the server node would conclude that the target information does not reside in any local IMCU, and would go to disk for the target information. The drawback to this approach is that the server node scans an indefinite number (which could be very high) of preceding leaf nodes to determine whether or not the target data is contained within a loaded IMCU. By having to scan an indeterminate number of leaf nodes, the time efficiency saved by loading target data into an IMCU is compromised by the time it takes to determine whether target data is loaded into an existing IMCU in local volatile memory.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.